/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._543;

/**
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
 * <p>
 * 示例 :
 * 给定二叉树
 * <p>
 * 1
 * / \
 * 2   3
 * / \
 * 4   5
 * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 * <p>
 * 注意：两结点之间的路径长度是以它们之间边的数目表示。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._543
 * @ClassName: DiameterTree
 * @Author: linyaonan
 * @Date: 2020/1/2 11:04
 */
public class DiameterTree {
    int max = 0;

    int maxDeep = 0;
    int maxValue = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getRealMax(root);
        return maxValue;
    }

    /**
     * 遍历每个节点，让每个节点作为根节点求左右最长路径
     *
     * @param node
     */
    private void getRealMax(TreeNode node) {
        if (node != null) {
            maxValue = Math.max(getMaxCount(node), maxValue);
            getRealMax(node.left);
            getRealMax(node.right);
        }
    }

    /**
     * 当前节点下左右最长路径
     *
     * @param root
     * @return
     */
    private int getMaxCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = bfs(root.left, 0);
        // 重置max
        max = 0;
        int right = bfs(root.right, 0);
        max = 0;
        return left + right;
    }

    /**
     * 路径bfs
     *
     * @param node
     * @param count
     * @return
     */
    private int bfs(TreeNode node, int count) {
        if (node == null) {
            max = Math.max(max, count);
        } else {
            count++;
            bfs(node.left, count);
            bfs(node.right, count);
        }
        return max;
    }

    /**
     * 找到二叉树最大直径
     * 通过分析最大直径肯定是一个子树的左子树+右子树组成
     * 所以遍历所有的子树，然后求出以当前子树为根，左子树最大与右子树最大和
     *
     * 整个过程有很多的重复判断，可以优化
     * @param root
     * @return
     */
    public int diameterOfBinaryTree2(TreeNode root) {
        // 1. 特殊情况
        if (root == null) {
            return 0;
        }
        bfs2(root);
        return maxDeep;
    }

    /**
     * bfs遍历整棵树
     * @param node
     */
    public void bfs2(TreeNode node) {
        if (node == null) {
            return;
        }
        bfs2(node.left);
        // 在当前节点时计算出以当前节点为根的最大子树和
        maxDeep = Math.max(getLeftAndRightDeep(node), maxDeep);
        bfs2(node.right);
    }

    public int getLeftAndRightDeep(TreeNode node) {
        return getMaxDeep(node.left, 0) + getMaxDeep(node.right, 0);
    }

    public int getMaxDeep(TreeNode node, int deep) {
        if (node == null) {
            return deep;
        }
        return Math.max(getMaxDeep(node.left, deep + 1), getMaxDeep(node.right, deep + 1));
    }

    int ans;

    /**
     * 还是上面解法2的思路，到一个节点时计算左右子树之和后与记录的最大值比较，返回的数值为当前节点最深的一根子树
     * @param root
     * @return
     */
    public int diameterOfBinaryTree3(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }

    public int depth(TreeNode node) {
        if (node == null) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }

}
